#include <vector> 
#include <cmath>
#include <stdio.h>
#include <iostream>
//#include <chrono>

int const INT_MAX = 1000;

using namespace std;

struct Coordenada
{
  int x;
  int y;
};

class Matriz
{  
public:
    vector<vector<float> > val;
    int n,k;
    Matriz();
};
Matriz::Matriz()
{
  Coordenada coord;
  vector<Coordenada> vecCord;
  cin >> n;
  cin >> k;
  val.resize(n);
  for(int i = 0; i < n; i++)
    val[i].resize(n);
  
  for(int j = 0; j < n; j++) // O(n)
  {
    cin >> coord.x;
    cin >> coord.y;
    vecCord.push_back(coord);
  }
  
  for(int i = 0; i < n; i++) 
    for(int j = 0; j < n; j++) // O(n^2)
      if(i != j)
      {
	val[i][j] = sqrt(pow(vecCord[i].x - vecCord[j].x,2) + pow(vecCord[i].y - vecCord[j].y,2));
      }
      else
	val[i][i] = 0;
}

int minKey(int n,float key[], bool mstSet[]) //O(n)
{
   int min = INT_MAX, min_index;
 
   for (int v = 0; v < n; v++)
     if (mstSet[v] == false && key[v] < min)
         min = key[v], min_index = v;
 
   return min_index;
}

int printMST(int parent[], int n, Matriz *matriz)
{
   cout << matriz->k <<" " << n - matriz->k << endl;
   for (int i = 0; i < n; i++)
     if(parent[i] == -1)
      cout << i + 1 << endl;
   for (int i = 0; i < n; i++)
     if(parent[i] != -1)
      cout << parent[i] + 1 << " " << i + 1 << endl;
}

void partirArbolenK(int *parent,float* key, Matriz *matriz) // O(k*n)
{
    int n = matriz->n;
    int k = matriz->k;
    for(int i = 1; i < k; i++)
    {
      float max = 0;
      int max_index = 0;
      for(int w = 0; w < n; w++)
      {
	if(parent[w] != -1)
	  if(key[w] > max)
	  {
	    max = key[w];
	    max_index = w;
	  } 
      }
      parent[max_index] = -1;
    } 
}

void primMinimumSpanningTree (Matriz *matriz)
{
     int n = matriz->val.size(); 
     int parent[n]; 
     float key[n];   
     bool mstSet[n];  
     
     for (int i = 0; i < n; i++)
        key[i] = INT_MAX, mstSet[i] = false;
 
     
     key[0] = 0;     
     parent[0] = -1;  
 
     for (int count = 0; count < n-1; count++)  
     {
        int u = minKey(n,key, mstSet); //O(n)
 
        mstSet[u] = true;
 
        for (int v = 0; v < n; v++)//O(n)
	if (matriz->val[u][v] && mstSet[v] == false && matriz->val[u][v] <  key[v])
             parent[v]  = u, key[v] = matriz->val[u][v];
     }
     
    partirArbolenK(parent, key, matriz);//O(n*k)
    
    printMST(parent, n, matriz); //O(n)
}

int chequearCasoTrivial(Matriz *matriz)
{
  if(matriz->n <= matriz->k)
  {
    cout << matriz->n << " 0" << endl;
    for(int i = 0; i < matriz->n; i++)
      cout << i + 1 << endl;
    return 1;
  }
  return 0;
}

int main()
{
  Matriz matriz = Matriz(); // O(n^2)
  // MEDICION TIEMPO
  //auto start = chrono::high_resolution_clock::now();
  // FIN MED
  if(chequearCasoTrivial(&matriz)) //O(n)
    return 0;
  primMinimumSpanningTree(&matriz); // con prim es o(n^2)
  // MED TIEMPO
  //auto finish = chrono::high_resolution_clock::now();
  //cout << chrono::duration_cast<chrono::microseconds>(finish - start).count() << endl;
  // FIN MED TIEMPO
  return 0;
}